/***********************************************************************
 * @file kcore_influential_communitySearch.cpp
 * Date         Author      description
 * ==========   =========   =======================================
 * 2023-07-14   Teng Long   xx
 *
 * @Copyright (C)  2023 
***********************************************************************/
/* Files includes  -----------------------------------------------------------*/
#include "kcore_influential_communitySearch.h"

/* Variables -----------------------------------------------------------------*/
struct Edge{
    int to,next;
    double w;
}edge_outNeighbor[edge_num], edge_inNeighbor[edge_num];
int head_outNeighbor[edge_num], head_inNeighbor[edge_num];
int cnt1 = 0, cnt2 = 0;
string authorName[node_num];
int outdeg[node_num];
int indeg[node_num];
int deg[node_num], coreNumber[node_num];
int bin[edge_num], vert[edge_num], pos[edge_num];
int indeg_global[node_num];
int outdeg_global[node_num];
int kmax = 0, lmax = 0;//max in-degree and max out-degree

int weight[node_num];
int flok[node_num], rk[node_num];
vector<set<int>> component;
int componenet_number = 0;
vector<set<int>> Result;
set<set<int>> newResult;

int temp_deg[node_num];
bool deleted[node_num];
queue<int> need_delete;
bool compvis[node_num];

/* Functions ----------------------------------------------------------------*/
void add_edge_outNeighbor(int u, int v, double w){
    edge_outNeighbor[++cnt1].to = v;
    edge_outNeighbor[cnt1].w = w;
    edge_outNeighbor[cnt1].next = head_outNeighbor[u];
    head_outNeighbor[u] = cnt1;
}

void add_edge_inNeighbor(int u, int v, double w){
    edge_inNeighbor[++cnt2].to = v;
    edge_inNeighbor[cnt2].w = w;
    edge_inNeighbor[cnt2].next = head_inNeighbor[u];
    head_inNeighbor[u] = cnt2;
}


void read_dataset(string DBLP_PATH, bool directed){

    /** 链式前向星中的表头初始化操作 **/
    for (int i = 0; i <= node_num; i++){
        head_outNeighbor[i] = -1;
        head_inNeighbor[i] = -1;
    }
    cnt1 = 0;
    cnt2 = 0;

    if(directed == 1){
        ifstream csv_data(DBLP_PATH, ios_base::in);
        if (!csv_data.is_open()){
            cout << "Error: opening file fail!" << endl;
            exit(1);
        }
        stringstream word_list;
        vector<double> words; //声明一个字符串向量
        string line;
        string word;

    //    int temp = 0, num = 0, author1, author2, old_author1, old_author2;
        int author1, author2;
        int ind = 0;
        int edge_have_val = 0;
        int topic_number = 0;
        double topic_value = 0.0;
        double w = 0.0;
        while(getline(csv_data, line)){
            stringstream word_list;
            words.clear();
            word_list << line;
    //        cout << line << endl;
            ind = 0;
            if(line[0] == 'a') continue;
            while(getline(word_list, word, ',')){
                ++ind;
                if(ind == 1) author1 = atoi(word.c_str());
                else if(ind == 2) authorName[author1] = word;
                else if(ind == 3) author2 = atoi(word.c_str());
                else if(ind == 4) authorName[author2] = word;
                else words.push_back(atof(word.c_str()));
            }
            // a -> b , 那么b的入度就要++，a的出度要++.
            // 并且， b 是 a 的outNeighbor, 相反a 是 b 的inNeighbor.
            indeg[author2]++;
            outdeg[author1]++;
            indeg_global[author2]++;
            outdeg_global[author1]++;
            deg[author1]++;
            deg[author2]++;
            kmax = max(kmax, indeg[author2]);
            lmax = max(lmax, outdeg[author1]);
            w = 1.0;
            add_edge_outNeighbor(author1, author2, w);// 存储out-neighbor
            add_edge_inNeighbor(author2, author1, w);// 这里存储登的为各个点的所有in-neighbor.

        }

        /** 可以根据kmax 及lmax的大小适当调整数组的大小 **/

        cout << "Maximal in-degree of the graph :" << kmax << endl;
        cout << "Maximal out-degree of the graph :" << lmax << endl;
    }
    else{
        ifstream csv_data(DBLP_PATH, ios_base::in);
        if (!csv_data.is_open()){
            cout << "Error: opening file fail!" << endl;
            exit(1);
        }
        stringstream word_list;
        vector<double> words; //声明一个字符串向量
        string line;
        string word;

    //    int temp = 0, num = 0, author1, author2, old_author1, old_author2;
        int author1, author2;
        int ind = 0;
        int edge_have_val = 0;
        int topic_number = 0;
        double topic_value = 0.0;
        double w = 0.0;
        while(getline(csv_data, line)){
            stringstream word_list;
            words.clear();
            word_list << line;
    //        cout << line << endl;
            ind = 0;
            if(line[0] == 'a') continue;
            while(getline(word_list, word, ',')){
                ++ind;
                if(ind == 1) author1 = atoi(word.c_str());
                else if(ind == 2) authorName[author1] = word;
                else if(ind == 3) author2 = atoi(word.c_str());
                else if(ind == 4) authorName[author2] = word;
                else words.push_back(atof(word.c_str()));
            }
            // a -> b , 那么b的入度就要++，a的出度要++.
            // 并且， b 是 a 的outNeighbor, 相反a 是 b 的inNeighbor.
            deg[author1]++;
            w = 1.0;
            kmax = max(kmax, deg[author2]);
            add_edge_outNeighbor(author1, author2, w);// 存储out-neighbor
            add_edge_inNeighbor(author2, author1, w);// 这里存储登的为各个点的所有in-neighbor.

        }
        /** 可以根据kmax 及lmax的大小适当调整数组的大小 **/
        cout << "Maximal in-degree of the graph :" << kmax << endl;
    }

    
}

void get_weight(string DBLP_PATH1, int n){
    /** 计算每个点的主题兴趣概率 为了后面可以对每个点的兴趣概率做一个统计，用来作图**/
    ifstream csv_data1(DBLP_PATH1, ios_base::in);
    if (!csv_data1.is_open()){
        cout << "Error: opening file fail!" << endl;
        exit(1);
    }

    priority_queue<pair<double,int>,vector<pair<double,int>>,greater<pair<double,int>>> que;

    stringstream word_list1;
    string line, word;
    int ind;
    line = "";
    word = "";
    int author_id;
    while(getline(csv_data1, line)){
        stringstream word_list1;
        word_list1 << line;
//        cout << line << endl;
        ind = 0;
        if(line[0] == 'a') continue;
        while(getline(word_list1, word, ',')){
            ++ind;
            if(ind == 1) author_id = atoi(word.c_str());
            else if(ind == 3) que.push(make_pair((atof(word.c_str())), author_id));
        }
    }
    csv_data1.close();

    /** 给权重排序，以相对顺序来对点的权值赋值。权值越高代表与在某主题下对别的点的影响力最高，传播期望大 **/
    int val = 0;
    while(!que.empty()){
        pair<double,int> top = que.top();que.pop();
//        cout << top.first << endl;
        weight[top.second] = ++val;
    }

   for (int v = 1; v <= n; v++){
//        weight_node_queue.push(make_pair(weight[v], v));
    //    cout << v <<' ' << authorName[v] << " 的贡献度分数为：" << weight[v] << endl;
    //    printf("点 %d 的贡献度分数为：%d\n", v, weight[v]);
    //    authorName
   }
//    for(int v = 1; v <= n; v++){
//         weight[v] = v;    
//    }

    cout << weight[2] << endl;
    cout << weight[3] << endl;
    return; 
}

set<int> get_K_Core(int k, int n){
    int max_degree = 0;
    for(int i = 1; i <= n; i++) {
        // cout << deg[i] << "$$" << endl;
        coreNumber[i] = deg[i];
        max_degree = max(max_degree, deg[i]);
    }
    for(int i = 0; i <= max_degree; i++) {
        bin[i] = 0;
    }
    for(int i = 1; i <= n; i++){
        bin[coreNumber[i]]++;
    }
    int start = 1;
    for(int i = 0; i <= max_degree; i++){
        int num = bin[i];
        bin[i] = start;//度0的第一个索引位置1， bin[1] = 4,度1的第一个索引位置为4.
        start += num;
    }
    for(int i = 1; i <= n; i++){
        pos[i] = bin[coreNumber[i]];//得到每个节点的bin[du] 即对应度的第一个索引位置。
        vert[pos[i]] = i;
        bin[coreNumber[i]]++;
    }
    for(int i = max_degree; i >= 1; i--) {
        bin[i] = bin[i-1];//给它变回去
    }
    bin[0] = 1;
    for(int i = 1; i <= n; i++){
        int u = vert[i];// pos 相当于是每个节点的座位号 节点越小度越小的话他的pos值就是[1,1+deg[0]], 这里的pos的 key就是结点i按度和
        //编号递增来排序后的位置，比如pos[1] = 1代表1结点sort后排第一，pos[2] = 2，2结点排第2，pos[3] = 10, 3结点排第10。
        //vert[i] 就是第i个位置的结点编号。这里的过程其实就相当与把度从小到大排好序了，桶排序。
        for (int k = head_outNeighbor[u]; ~k; k = edge_outNeighbor[k].next){
            int v = edge_outNeighbor[k].to;
            if(coreNumber[v] > coreNumber[u]){
                int dv = coreNumber[v], pv = pos[v];
                int pw = bin[dv], w = vert[pw];
                if(v != w){
                    pos[v] = pw; vert[pv] = w;//
                    pos[w] = pv; vert[pw] = v;
                }
                bin[dv]++;
                coreNumber[v]--;
            }
        }
    }
    set<int> graph;
    // for(int i = 1; i <= n; i++) printf("%d\n",coreNumber[i]);
    //例如，3-core，就是deg[i] >= 3的集合。
    for(int i = 1;i <= n; i++){
        if(coreNumber[i] >= k){
            graph.insert(i);
        }
    }
    return graph;
}

int Find(int x){
    return x == flok[x] ? x : flok[x] = Find(flok[x]);
}

void Union(int x, int y){
    int t1 = Find(x), t2 = Find(y);
    if(t1 == t2)return;
    if(rk[t1] > rk[t2])flok[t2] = t1;
    else{
        if(rk[t1] == rk[t2]) rk[t2]++;
        flok[t1] = t2;
    }
}

void connected_components_search(set<int> seed, int n){
    //并查集的准备
    for (int i = 1;i <= n; i++){
        flok[i] = i;rk[i] = 0;
    }
    bool *vis = new bool[node_num]();
    bool *seed_vis = new bool[node_num]();
    set<int>::iterator iter = seed.begin();
    int x, now, to;

    //下面是把传入的集合内的元素置1， 为的是后面只对集合内的元素进行操作。
    while(iter != seed.end()){
        x = (*iter);
        seed_vis[x] = 1;
        iter++;
    }

    //BFS + 并查集， 把core中的社区找出来，每个社区要满足三个特性连通等等。
    iter = seed.begin();
    while(iter != seed.end()){
        x = (*iter);
        if(vis[x] == 0){
            // BFS:
            queue<int> que;
            que.push(x);
            vis[x] = 1;
            while(!que.empty()){
                now = que.front();
                que.pop();
                for (int k = head_outNeighbor[now]; ~k; k = edge_outNeighbor[k].next){
                    to = edge_outNeighbor[k].to;
                    if(vis[to] == true)continue;
                    if(seed_vis[to] == false)continue;
                    Union(x, to);
                    que.push(to);
                    vis[to] = 1;
                }
                for (int k = head_inNeighbor[now]; ~k; k = edge_inNeighbor[k].next){
                    to = edge_inNeighbor[k].to;
                    if(vis[to] == true)continue;
                    if(seed_vis[to] == false)continue;
                    Union(x, to);
                    que.push(to);
                    vis[to] = 1;
                }
            }
        }
        iter++;
    }


//    iter = seed.begin();
//    while(iter != seed.end()){
//        cout << (*iter) <<' ' << flok[(*iter)] << ' ' <<vis[(*iter)] << endl;
//        iter++;
//    }

    // 获取每个community 的 flok值。不同flok值的个数就是不同集合的个数
    vector<int> component_index;
    iter = seed.begin();
    while(iter != seed.end()){
        x = (*iter);
        if(x == flok[x]){
            component_index.push_back(flok[x]);
        }
        iter++;
    }
    componenet_number = component_index.size();
//    cout << "componenet_number: " << componenet_number << endl;
    for (int i = 0; i < componenet_number; i++) {
		set<int> s;
		component.push_back(s);
	}

	// 统计每个influential community的元素，存储到communities里面。
	for (int i = 0; i < componenet_number; i++){
        iter = seed.begin();
        while(iter != seed.end()){
            x = (*iter);
            if(flok[x] == component_index[i]){
                component[i].insert(x);
            }
            iter++;
        }
	}
    delete[] vis;
    delete[] seed_vis;
    return;
}


void calc_new_degree(vector<int> &comp, int k, int n){
    int Size = comp.size();
    bool *vis = new bool[n+10]();
    for(int i = 0; i < comp.size(); i++){
        vis[comp[i]] = true;
        compvis[comp[i]] = true;
    }

    for(int i = 1;i <= n; i++){
        if(vis[i] == false)continue;
        for(int k = head_outNeighbor[i]; ~k; k = edge_outNeighbor[k].next){
            int to = edge_outNeighbor[k].to;
            if(vis[to] == true){
                temp_deg[to]++;
            }
        }
    }
    delete[] vis;
    return;
}

void UPDATE(int v, int k){
    if(deleted[v] == true) return;
    if(deleted[v] == false){
        deleted[v] = true;
        temp_deg[v] = 0;
        for (int j = head_outNeighbor[v]; ~j; j = edge_outNeighbor[j].next){
            int outNeighbor = edge_outNeighbor[j].to;
            if(compvis[outNeighbor] == false)continue;
            if(deleted[outNeighbor] == false){
                temp_deg[outNeighbor] -= 1;
                if(temp_deg[outNeighbor] < k){
                    UPDATE(outNeighbor, k);
                }
            }
        }
        
//        cout << "UPDATE里删除的点" << v << endl;
        need_delete.push(v);
//        delete_node(v);
    }
    return ;
}


void delete_edge(int u, int v){
    /** 把点u对v的 outNeighber edge delete掉 相当于只删除了u的表**/
    int pre = head_outNeighbor[u];
    if(pre != -1){
        if(edge_outNeighbor[pre].to == v) {
            head_outNeighbor[u] = edge_outNeighbor[pre].next;
            edge_outNeighbor[pre].next = -1;
            edge_outNeighbor[pre].to = 0;
            edge_outNeighbor[pre].w = 0.0;
        }
        else{
            for (int k = edge_outNeighbor[head_outNeighbor[u]].next; ~k; k = edge_outNeighbor[k].next){
                int to = edge_outNeighbor[k].to;
                if(to == v){
                    edge_outNeighbor[pre].next = edge_outNeighbor[k].next;
                    edge_outNeighbor[k].next = -1;
                    edge_outNeighbor[k].to = 0;
                    edge_outNeighbor[k].w = 0.0;
                    break;
                }
                pre = k;
            }
        }
    }

    /** 把点u对v的 inNeighbor edge delete掉 相当于只删除了u的表***/
    pre = head_inNeighbor[u];
    if(pre != -1){
        if(edge_inNeighbor[pre].to == v) {
            head_inNeighbor[u] = edge_inNeighbor[pre].next;
            edge_inNeighbor[pre].next = -1;
            edge_inNeighbor[pre].to = 0;
            edge_inNeighbor[pre].w = 0.0;
        }
        else{
            for (int k = edge_inNeighbor[head_inNeighbor[u]].next; ~k; k = edge_inNeighbor[k].next){
                int to = edge_inNeighbor[k].to;
                if(to == v){
                    edge_inNeighbor[pre].next = edge_inNeighbor[k].next;
                    edge_inNeighbor[k].next = -1;
                    edge_inNeighbor[k].to = 0;
                    edge_inNeighbor[k].w = 0.0;
                    break;
                }
                pre = k;
            }
        }
    }
    return;
}

void delete_node(int delete_node){

    temp_deg[delete_node] = 0;
    deg[delete_node] = 0;
    //更新删除结点关联边的出入度和关联点的存储表
    queue<int>que1, que2;
    for (int k = head_outNeighbor[delete_node]; ~k; k = edge_outNeighbor[k].next){
        int to = edge_outNeighbor[k].to;
        que1.push(to);
    }
    for (int k = head_inNeighbor[delete_node]; ~k; k = edge_inNeighbor[k].next){
        int to = edge_inNeighbor[k].to;
        que2.push(to);
    }
    while(!que1.empty()){
        int to = que1.front();
        que1.pop();
        delete_edge(delete_node, to);
        deg[to] = max(0, deg[to] - 1);
        // temp_deg[to] = max(0, temp_deg[to] - 1);
        delete_edge(to, delete_node);
    }
    while(!que2.empty()){
        int to = que2.front();
        que2.pop();
        delete_edge(delete_node, to);
        delete_edge(to, delete_node);
    }

    head_inNeighbor[delete_node] = -1;
    head_outNeighbor[delete_node] = -1;

    return;
}

void influential_community_search(set<int> &seed, int n){
    // 这里的影响力搜索其实相当于在无向图进行处理
    // 即只要有边，不管是出边还是入边，我就给他们union。得出的结果满足弱连通
    //并查集的准备
    for (int i = 1;i <= n; i++){
        flok[i] = i;rk[i] = 0;
    }
    bool *vis = new bool[node_num]();
    bool *seed_vis = new bool[node_num]();
    set<int>::iterator iter = seed.begin();
    int x, now, to;

    //下面是把传入的集合内的元素置1， 为的是后面只对集合内的元素进行操作。
    while(iter != seed.end()){
        x = (*iter);
        seed_vis[x] = 1;
        iter++;
    }

    //BFS + 并查集， 把core中的社区找出来，每个社区要满足三个特性连通等等。
    iter = seed.begin();
    while(iter != seed.end()){
        x = (*iter);
        if(vis[x] == 0){
            // BFS:
            queue<int> que;
            que.push(x);
            vis[x] = 1;
            while(!que.empty()){
                now = que.front();
                que.pop();
                for (int k = head_outNeighbor[now]; ~k; k = edge_outNeighbor[k].next){
                    to = edge_outNeighbor[k].to;
                    if(vis[to] == true)continue;
                    if(seed_vis[to] == false)continue;
                    Union(x, to);
                    que.push(to);
                    vis[to] = 1;
                }
                for (int k = head_inNeighbor[now]; ~k; k = edge_inNeighbor[k].next){
                    to = edge_inNeighbor[k].to;
                    if(vis[to] == true)continue;
                    if(seed_vis[to] == false)continue;
                    Union(x, to);
                    que.push(to);
                    vis[to] = 1;
                }
            }
        }
        iter++;
    }


//    iter = seed.begin();
//    while(iter != seed.end()){
//        cout << (*iter) <<' ' << flok[(*iter)] << ' ' <<vis[(*iter)] << endl;
//        iter++;
//    }

    // 获取每个community 的 flok值。不同flok值的个数就是不同集合的个数
    vector<int> community_index;
    vector<set<int>> community;
    int community_number = 0;
    iter = seed.begin();
    while(iter != seed.end()){
        x = (*iter);
        if(x == flok[x]){
            community_index.push_back(flok[x]);
        }
        iter++;
    }
    community_number = community_index.size();
//    cout << "community_number: " << community_number << endl;
    for (int i = 0; i < community_number; i++) {
		set<int> s;
		community.push_back(s);
	}

	// 统计每个influential community的元素，存储到communities里面。
	for (int i = 0; i < community_number; i++){
        iter = seed.begin();
        while(iter != seed.end()){
            x = (*iter);
            if(flok[x] == community_index[i]){
//                cout << x << ' ' << outdeg[x] << ' ' <<  eta_outdeg[x] << ',' << eta_K_outdeg[x] << endl;;
                community[i].insert(x);
            }
            iter++;
        }
//        cout << endl;
        Result.push_back(community[i]);
	}


    delete[] vis;
    delete[] seed_vis;
    return;
}

void Kcore_influential_Community_Search(int k, int n){
/**  迭代删除最小点 **/

    set<int> graph;
    graph = get_K_Core(k, n);
    connected_components_search(graph, n);
    set<int> k_core;
    set<int>::iterator iter;
    for(int i = 0; i < componenet_number; i++){
        iter = component[i].begin();
//        cout << "Size: " << component[i].size() << endl;
        Result.push_back(component[i]);
        vector<int> comp;
        priority_queue<pair<int,int>, vector<pair<int,int> >, greater<pair<int,int> > > weight_node_queue;
        while(iter != component[i].end()){
            int v = (*iter);comp.push_back(v);
            weight_node_queue.push(make_pair(weight[v], v));
//            printf("点 %d 的影响力分数为：%d\n", v, weight[v]);
            iter++;
        }

        // 给eta_K_outdeg排序，队头是度最小的点，看他的度是否大于等于 qeury_l
        priority_queue<pair<int,int>, vector<pair<int,int> >, greater<pair<int,int> > > que;
        
        // memset(compvis,false,sizeof(compvis));
        calc_new_degree(comp, k, n);

        /** 对每个组件，进一步计算k-core **/
        while(!weight_node_queue.empty()){

            pair<int,int> top = weight_node_queue.top();
            int min_weight_node = top.second;
            int w = top.first;


        //    cout << "删除点" << min_weight_node << endl;
            if(deleted[min_weight_node] == true) {
                weight_node_queue.pop();
                continue;
            }

            /** 删除权值最小点 **/ // 边没有删干净
            UPDATE(min_weight_node, k);

            while(!need_delete.empty()){
                int need_delete_node = need_delete.front();
                delete_node(need_delete_node);
                need_delete.pop();
            }

            /** 删除点后的入出度更新一下 **/

            // for(int i = 1; i <= n; i++){
            //     deg[i] = temp_deg[i];
            // }

            /** 获取删除点后的(k,l,eta)-core, 并搜索community**/
            k_core.clear();
            for (int i = 0; i < comp.size(); i++){
                if(deleted[comp[i]] == false) {
                    // cout << comp[i] << ' ';
                    k_core.insert(comp[i]);
                }
            }
            // cout << endl;

            if(k_core.size() == 0) break;//没有满足的k-core了。

            influential_community_search(k_core, n);

            weight_node_queue.pop();
        }
        for(int i = 0; i < comp.size(); i++){
            compvis[comp[i]] = false;
        }
	}

    //去重
    for(int i = 0; i < Result.size(); i++){
        newResult.insert(Result[i]);
    }
    Result.clear();
    set<set<int>>::iterator it;
    for (it = newResult.begin(); it != newResult.end(); it++){
        set<int> temp = (*it);
        Result.push_back(temp);
    }

    vector<set<int>> Res;
    int yuzhi = 27000;
    
    priority_queue <pair<int,int>> queue;
    for(int i = 0; i < newResult.size(); i++){
        set<int>::iterator iter = Result[i].begin();
        // cout << k << "-Influential ";
        // std::cout << "Community Size: " << Result[i].size() << endl;

        iter = Result[i].begin();
        int is = n;
        while(iter != Result[i].end()){
            // std::cout << (*iter) << ' ' << authorName[(*iter)] << endl;
            is = min(is, weight[(*iter)]);
            iter++;
        }
        queue.push(make_pair(is,i));
        // std::cout << "社区贡献度 :  " << is << endl;
        if(is > yuzhi){
            Res.push_back(Result[i]);
        }
        // std::cout << endl;
    }

    for (int i = 0; i < Res.size(); i++){
        cout << "第 " << i + 1 << " 个" << "高贡献度团队（社区）:" << endl;
        set<int> com = Res[i];
        set<int>::iterator it = com.begin();
        int is = n;
        while(it != com.end()){
            cout << (*it) << ' ' << authorName[(*it)] << endl;
            is = min(is, weight[(*it)]);
            it++;
        }
        cout << "社区贡献度 :  " << is << endl;      
        cout << endl;  
    }

    printf("贡献度超过 阈值%d 的%d-core高贡献社区有%d个", yuzhi, k, Res.size());


//     /**  迭代删除最小点 **/

//     set<int> graph;
//     graph = get_K_Core(k, n);
//     connected_components_search(graph, n);
//     set<int> k_core;
//     set<int>::iterator iter;
//     for(int i = 0; i < componenet_number; i++){
//         iter = component[i].begin();
// //        cout << "Size: " << component[i].size() << endl;
//         Result.push_back(component[i]);
//         vector<int> comp;
//         priority_queue<pair<int,int>, vector<pair<int,int> >, greater<pair<int,int> > > weight_node_queue;
//         while(iter != component[i].end()){
//             int v = (*iter);comp.push_back(v);
//             weight_node_queue.push(make_pair(weight[v], v));
// //            printf("点 %d 的影响力分数为：%d\n", v, weight[v]);
//             iter++;
//         }

//         // 给eta_K_outdeg排序，队头是度最小的点，看他的度是否大于等于 qeury_l
//         priority_queue<pair<int,int>, vector<pair<int,int> >, greater<pair<int,int> > > que;
        
//         calc_new_degree(comp, k, n);

//         /** 对每个组件，进一步计算k-core **/
//         while(!weight_node_queue.empty()){

//             pair<int,int> top = weight_node_queue.top();
//             int min_weight_node = top.second;
//             int w = top.first;


//         //    cout << "删除点" << min_weight_node << endl;
//             if(deleted[min_weight_node] == true) {
//                 weight_node_queue.pop();
//                 continue;
//             }

//             /** 删除权值最小点 **/ // 边没有删干净
//             UPDATE(min_weight_node, k);

//             while(!need_delete.empty()){
//                 int need_delete_node = need_delete.front();
//                 delete_node(need_delete_node);
//                 need_delete.pop();
//             }

//             /** 删除点后的入出度更新一下 **/
//             for(int i = 1; i <= n; i++){
//                 deg[i] = temp_deg[i];
//             }

//             /** 获取删除点后的(k,l,eta)-core, 并搜索community**/
//             k_core.clear();
//             for (int i = 0; i < comp.size(); i++){
//                 if(deleted[comp[i]] == false) {
//                     // cout << comp[i] << ' ';
//                     k_core.insert(comp[i]);
//                 }
//             }
//             // cout << endl;

//             if(k_core.size() == 0) break;//没有满足的k-core了。

//             influential_community_search(k_core, n);

//             weight_node_queue.pop();
//         }
// 	}

//     //去重
//     for(int i = 0; i < Result.size(); i++){
//         newResult.insert(Result[i]);
//     }
//     Result.clear();
//     set<set<int>>::iterator it;
//     for (it = newResult.begin(); it != newResult.end(); it++){
//         set<int> temp = (*it);
//         Result.push_back(temp);
//     }


//     priority_queue <pair<int,int>> queue;
//     for(int i = 0; i < Result.size(); i++){
//         set<int>::iterator iter = Result[i].begin();

//         // if(Result[i].size() > k)continue;
//         cout << i + 1 << ' ' << k << "-Influential ";
//         std::cout << "Community Size: " << Result[i].size() << endl;

//         iter = Result[i].begin();
//         int is = n;
//         while(iter != Result[i].end()){
//             std::cout << (*iter) << ' ' << authorName[(*iter)] << endl;
//             // cout << deg[(*iter)] << endl;
//             is = min(is, weight[(*iter)]);
//             iter++;
//         }
//         queue.push(make_pair(is,i));
//         std::cout << "社区贡献度 :  " << is << endl;
//         std::cout << endl;
//     }

}

void Kcore_Community_Search(int k, int n){
    /**  迭代删除最小点 **/
    clock_t start,finish;
    start = clock();

    cout << "无向图协作网络中，合作密集的团队（社区）个数:  " << componenet_number << endl;
    
    set<int> graph;
    graph = get_K_Core(k, n);
    connected_components_search(graph, n);

    
    set<int>::iterator iter;
    for(int i = 0; i < componenet_number; i++){
        iter = component[i].begin();
        cout << "K-core " << i+1 << endl;
        cout << "Size: " << component[i].size() << endl;

        cout << "node set: " << endl;
        cout << "----------------" << endl;
        while(iter != component[i].end()){
            int v = (*iter);
            cout << v << ' ' << authorName[v] << endl;
            iter++;
        }
        cout << "----------------" << endl;
	}
    finish = clock();

    cout << "无向图协作网络中，合作密集的团队（社区）个数:  " << componenet_number << endl;
    std::cout << "time:  " <<  setprecision(10) << (finish-start) / CLOCKS_PER_SEC << endl;// / CLOCKS_PER_SEC
    
    ofstream out1("C:/Users/pc/Desktop/homework/Dataset/DBLP/topo"+to_string(k)+"_"+"Core_node.csv");
    ofstream out2("C:/Users/pc/Desktop/homework/Dataset/DBLP/topo"+to_string(k)+"_"+"Core_edge.csv");
    out1 << "source" <<','<<"node_label"<<','<<"node_size"<<','<<"share_1"<<','<<"share_2"<<endl;
    out2 << "target" << ',' << "source" << endl;

    string DBLP_DB_PATH = "C:/Users/pc/Desktop/homework/Dataset/DBLP/DB_27097_195996_Graph.csv";
    string DBLP_DM_PATH = "C:/Users/pc/Desktop/homework/Dataset/DBLP/DM_49831_319396_Graph.csv";
    
    read_dataset(DBLP_DM_PATH, 0);

    bool *visit = new bool[node_num]();//标记community 中的结点。

    // int community_number = Result.size();
    int  influence_score = n;
    for(int i = componenet_number-2;i < componenet_number; i++){
        set<int> community = component[i];
        set<int>::iterator iter = community.begin();
        int temp_id = 0;
        double sum = 1.0;
        while(iter != community.end()){
            temp_id = (*iter);
            // cout << temp_id << ":" << authorName[temp_id] <<  ' ' << endl;
            out1 << temp_id << ',' << authorName[temp_id] << ',' << 1.0;
            visit[temp_id] = true;
    //        sum = 1.0;
    //        for (int j = 0; j < author_topic_distribution[temp_id].size(); j++){
    //            out1 << ',' << author_topic_distribution[temp_id][j];
    //            sum -= author_topic_distribution[temp_id][j];
    //        }
    //        out1 << ',' << sum << endl;
            out1 << endl;
            influence_score = min(influence_score, weight[temp_id]);
            iter++;
        }

        iter = community.begin();
        while(iter != community.end()){
            int temp_id = (*iter);
            for(int j = head_outNeighbor[temp_id]; ~j; j = edge_outNeighbor[j].next){
                int to = edge_outNeighbor[j].to;
                if(visit[to] == true){
                   out2 << to << ',' << temp_id << endl;    
                //    std::cout << to << ',' << temp_id << endl;            
                }
            }
            iter++;
        }
    }
    delete[] visit;
    out1.close();
    out2.close();
    return;

}

void top_r_Kcore_influential_Community_Search(int k, int n, int r){
/**  迭代删除最小点 **/

    set<int> graph;
    graph = get_K_Core(k, n);
    connected_components_search(graph, n);
    set<int> k_core;
    set<int>::iterator iter;
    for(int i = 0; i < componenet_number; i++){
        iter = component[i].begin();
//        cout << "Size: " << component[i].size() << endl;
        Result.push_back(component[i]);
        vector<int> comp;
        priority_queue<pair<int,int>, vector<pair<int,int> >, greater<pair<int,int> > > weight_node_queue;
        while(iter != component[i].end()){
            int v = (*iter);comp.push_back(v);
            weight_node_queue.push(make_pair(weight[v], v));
//            printf("点 %d 的影响力分数为：%d\n", v, weight[v]);
            iter++;
        }

        // 给eta_K_outdeg排序，队头是度最小的点，看他的度是否大于等于 qeury_l
        priority_queue<pair<int,int>, vector<pair<int,int> >, greater<pair<int,int> > > que;
        
        // memset(compvis,false,sizeof(compvis));
        calc_new_degree(comp, k, n);

        /** 对每个组件，进一步计算k-core **/
        while(!weight_node_queue.empty()){

            pair<int,int> top = weight_node_queue.top();
            int min_weight_node = top.second;
            int w = top.first;


        //    cout << "删除点" << min_weight_node << endl;
            if(deleted[min_weight_node] == true) {
                weight_node_queue.pop();
                continue;
            }

            /** 删除权值最小点 **/ // 边没有删干净
            UPDATE(min_weight_node, k);

            while(!need_delete.empty()){
                int need_delete_node = need_delete.front();
                delete_node(need_delete_node);
                need_delete.pop();
            }

            /** 删除点后的入出度更新一下 **/

            // for(int i = 1; i <= n; i++){
            //     deg[i] = temp_deg[i];
            // }

            /** 获取删除点后的(k,l,eta)-core, 并搜索community**/
            k_core.clear();
            for (int i = 0; i < comp.size(); i++){
                if(deleted[comp[i]] == false) {
                    // cout << comp[i] << ' ';
                    k_core.insert(comp[i]);
                }
            }
            // cout << endl;

            if(k_core.size() == 0) break;//没有满足的k-core了。

            influential_community_search(k_core, n);

            weight_node_queue.pop();
        }
        for(int i = 0; i < comp.size(); i++){
            compvis[comp[i]] = false;
        }
	}

    //去重
    for(int i = 0; i < Result.size(); i++){
        newResult.insert(Result[i]);
    }
    Result.clear();
    set<set<int>>::iterator it;
    for (it = newResult.begin(); it != newResult.end(); it++){
        set<int> temp = (*it);
        Result.push_back(temp);
    }


    priority_queue <pair<int,int>> queue;
    for(int i = 0; i < newResult.size(); i++){
        set<int>::iterator iter = Result[i].begin();
        // cout << k << "-Influential ";
        // std::cout << "Community Size: " << Result[i].size() << endl;

        iter = Result[i].begin();
        int is = n;
        while(iter != Result[i].end()){
            // std::cout << (*iter) << ' ' << authorName[(*iter)] << endl;
            is = min(is, weight[(*iter)]);
            iter++;
        }
        queue.push(make_pair(is,i));
        // std::cout << "社区贡献度 :  " << is << endl;
        // std::cout << endl;
    }

    int community_number = -1;
    int ind = 0;
    while(!queue.empty()){
        int id = queue.top().second;
        int IS = queue.top().first;
        queue.pop();
        if(community_number == -1) community_number = id;
        set<int>::iterator iter = Result[id].begin();
        std::cout << "community Size: " << Result[id].size() << endl;
        while(iter != Result[id].end()){
            std::cout << (*iter) << ' ' << authorName[(*iter)] << endl;
            iter++;
        }
        printf("社区贡献度:  %d\n", IS);
        // std::cout << "influence score:  " << IS << endl;
        cout << endl;
        ++ind;
        if(ind >= r)break;
    }



    ofstream out1("C:/Users/pc/Desktop/homework/Dataset/DBLP/"+to_string(k)+"_"+"Core_node.csv");
    ofstream out2("C:/Users/pc/Desktop/homework/Dataset/DBLP/"+to_string(k)+"_"+"Core_edge.csv");
    out1 << "source" <<','<<"node_label"<<','<<"node_size"<<','<<"share_1"<<','<<"share_2"<<endl;
    out2 << "target" << ',' << "source" << endl;

    bool *visit = new bool[node_num]();//标记community 中的结点。
    
    cout << Result[community_number].size() << endl;
    // int community_number = Result.size();
    int  influence_score = n;
    for(int i = community_number;i < community_number+1; i++){
        set<int> community = Result[i];
        set<int>::iterator iter = community.begin();
        int temp_id = 0;
        double sum = 1.0;
        while(iter != community.end()){
            temp_id = (*iter);
            // cout << temp_id << ":" << authorName[temp_id] <<  ' ' << endl;
            out1 << temp_id << ',' << authorName[temp_id] << ',' << 1.0;
            visit[temp_id] = true;
    //        sum = 1.0;
    //        for (int j = 0; j < author_topic_distribution[temp_id].size(); j++){
    //            out1 << ',' << author_topic_distribution[temp_id][j];
    //            sum -= author_topic_distribution[temp_id][j];
    //        }
    //        out1 << ',' << sum << endl;
            out1 << endl;
            influence_score = min(influence_score, weight[temp_id]);
            iter++;
        }


        string DBLP_DB_PATH = "C:/Users/pc/Desktop/homework/Dataset/DBLP/DB_27097_195996_Graph.csv";
        string DBLP_DM_PATH = "C:/Users/pc/Desktop/homework/Dataset/DBLP/DM_49831_319396_Graph.csv";
    
        read_dataset(DBLP_DM_PATH, 0);

        iter = community.begin();
        while(iter != community.end()){
            int temp_id = (*iter);
            for(int j = head_outNeighbor[temp_id]; ~j; j = edge_outNeighbor[j].next){
                int to = edge_outNeighbor[j].to;
                if(visit[to] == true){
                   out2 << to << ',' << temp_id << endl;    
                //    std::cout << to << ',' << temp_id << endl;            
                }
            }
            iter++;
        }

        delete[] visit;
    }

    out1.close();
    out2.close();
    return;
}


void dataForGraph(int k, int n){
    ofstream out1("C:/Users/pc/Desktop/homework/Dataset/DBLP/"+to_string(k)+"_"+"Core_node.csv");
    ofstream out2("C:/Users/pc/Desktop/homework/Dataset/DBLP/"+to_string(k)+"_"+"Core_edge.csv");
    out1 << "source" <<','<<"node_label"<<','<<"node_size"<<','<<"share_1"<<','<<"share_2"<<endl;
    out2 << "target" << ',' << "source" << endl;

    bool *visit = new bool[node_num]();//标记community 中的结点。
    
    int community_number = Result.size();
    int  influence_score = n;
    for(int i = max(community_number-1, 0);i < community_number; i++){
        set<int> community = Result[i];
        set<int>::iterator iter = community.begin();
        int temp_id = 0;
        double sum = 1.0;
        while(iter != community.end()){
            temp_id = (*iter);
            // cout << temp_id << ":" << authorName[temp_id] <<  ' ' << endl;
            out1 << temp_id << ',' << authorName[temp_id] << ',' << 1.0;
            visit[temp_id] = true;
    //        sum = 1.0;
    //        for (int j = 0; j < author_topic_distribution[temp_id].size(); j++){
    //            out1 << ',' << author_topic_distribution[temp_id][j];
    //            sum -= author_topic_distribution[temp_id][j];
    //        }
    //        out1 << ',' << sum << endl;
            out1 << endl;
            influence_score = min(influence_score, weight[temp_id]);
            iter++;
        }


        string DBLP_DB_PATH = "C:/Users/pc/Desktop/homework/Dataset/DBLP/DB_27097_195996_Graph.csv";
        string DBLP_DM_PATH = "D:/a_work1_C++/dataset/NEW_DBLP/DM_49831_319396_Graph.csv";
    
        read_dataset(DBLP_DB_PATH, 0);

        iter = community.begin();
        while(iter != community.end()){
            int temp_id = (*iter);
            for(int j = head_outNeighbor[temp_id]; ~j; j = edge_outNeighbor[j].next){
                int to = edge_outNeighbor[j].to;
                if(visit[to] == true){
                   out2 << to << ',' << temp_id << endl;    
                //    std::cout << to << ',' << temp_id << endl;            
                }
            }
            iter++;
        }

        delete[] visit;
    }

    out1.close();
    out2.close();
    return;
}